package com.fw.structure.tree;

import lombok.Data;
import lombok.ToString;

/**
 * 线索二叉树
 * 总结 线索二叉树出于什么目的性, 用来 将左右空节点 进行实际关联操作，避免浪费节点的形式。
 *    产生 左前驱，右后继的形式
 */
public class ThreadBinaryTreeDemo {

    public static void main(String[] args) {
        ThreadBinaryNode root = new ThreadBinaryNode(1, "tom");
        ThreadBinaryNode node2 = new ThreadBinaryNode(3, "jack");
        ThreadBinaryNode node3 = new ThreadBinaryNode(6, "smith");
        ThreadBinaryNode node4 = new ThreadBinaryNode(8, "mary");
        ThreadBinaryNode node5 = new ThreadBinaryNode(10, "king");
        ThreadBinaryNode node6 = new ThreadBinaryNode(14, "dim");


        root.setLeftNode(node2);
        root.setRightNode(node3);
        node2.setLeftNode(node4);
        node2.setRightNode(node5);
        node3.setLeftNode(node6);

        ThreadBinaryTree threadBinaryTree = new ThreadBinaryTree(root);

        threadBinaryTree.threadedNodes(root);
        System.out.println(node6);

        threadBinaryTree.threadedList();

    }
}



/**
 * 实际线索二叉树原型
 */
class  ThreadBinaryTree{
   // 根节点
    ThreadBinaryNode root;
   // 线索化，记载节点上的夫节点。
    ThreadBinaryNode perNode;

    public ThreadBinaryTree(ThreadBinaryNode root) {
        this.root = root;
    }

    public ThreadBinaryTree() {
    }

    public void threadedNodes(){
        threadedNodes(root);
    }

    // 线索化遍历二叉树
 public void  threadedList(){
        //1. 赋值给临时变量
     ThreadBinaryNode node = root;
        //2. 特定条件
     while (node != null){
         // 3. 先找到前驱节点
         while (node.getLeftType() == 0){
             // 就将该节点赋值到当前节点
             node = node.getLeftNode();
         }
         // 直接输出
         System.out.println(node);
         // 找到 后继节点 就直接输出
         while (node.getRightType() == 1){
             node = node.getRightNode();
             System.out.println(node);
         }
         node = node.getRightNode();
     }

 }

    // 中序优化线索二叉树
 public void threadedNodes(ThreadBinaryNode node){
     // 对该 node 进行  优化
     if (node == null)
         return;

     // 左节点建立线索
     threadedNodes(node.getLeftNode());

     //进行建立线索概念
     //第一步 当前前驱节点如果是空，代表当前节点的 是没有左子树的，可以建立链接
     //第二步，如果当前节点是空，代表可以建立前驱节点

     // 1. 首先判断该节点的前驱节点是否需要建立
     if (node.getLeftNode() == null){
         node.setLeftNode(perNode);
         node.setLeftType(1);
     }
     // 第四步，此node 是当前节点，那么perNode 就是中序遍历 顺序的 当前节点  前一个节点
     // 第五步，如果前一个节点不是空，并且他的右节点是空的话，就相当于是找到了 需要后继节点的目标
     // 第六步，找到之后，将前一个节点 的右子树指向当前节点，完成后继操作。

     //2. 后继节点
     if (perNode != null && perNode.getRightNode() == null){
         perNode.setRightNode(node);
         perNode.setRightType(1);
     }
     // 第三步，将当前节点指向前面这个前驱节点，因为不断的递归，需要创建临时节点 才能完善前驱节点和后继节点的操作
     perNode = node;

     //右节点建立线索
     threadedNodes(node.getRightNode());


 }


}

/**
 * 二叉树节点
 * 分为 左节点 右节点等
 */
@Data
@ToString
class ThreadBinaryNode {

    // 节点姓名
    private String nodeName;

    // 节点 编号
    private int noNumber;

    //说明
//1. 如果 leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点
//2. 如果 rightType == 0 表示指向是右子树, 如果 1 表示指向后继结点
    private int leftType;
    private int rightType;

    public ThreadBinaryNode(String nodeName, int noNumber) {
        this.nodeName = nodeName;
        this.noNumber = noNumber;
    }

    public ThreadBinaryNode(int noNumber,String nodeName) {
        this.nodeName = nodeName;
        this.noNumber = noNumber;
    }

    // 分为 左节点
    @ToString.Exclude
    private ThreadBinaryNode leftNode;
    // 以及 右节点
    @ToString.Exclude
    private ThreadBinaryNode rightNode;

  }